Добро пожаловать на урок 3 в курсе Концепции искусственного интеллекта (Политехнический университет, курс COMP5511). В этом уроке мы переходим от одиночного агентного поиска пути к адверсарному поиску, где агенты действуют в конкурирующих многоагентных средах. Мы также представляем задачи удовлетворения ограничений (CSP), парадигме, при которой цель — найти состояние, которое удовлетворяет определённому набору ограничений, а не пройти путь.
Основные понятия
- Адверсарный поиск: Опирается на алгоритмы, такие как Минимакс и отсечение Альфа-Бета для принятия рациональных решений против разумного противника.
- Поиск дерева Монте-Карло (MCTS): Изучает вероятностное принятие решений, являясь основой современных игровых ИИ, таких как AlphaGo.
- Удовлетворение ограничений: Моделирует задачи с помощью переменных, областей и ограничений, решаемые с помощью обратного прохода и локального поиска.
Анализ сложности
В адверсарных условиях сложность пространства поиска часто определяется коэффициентом ветвления игры
Предупреждение о смене парадигмы
В отличие от стандартного поиска (например, A* или BFS), где среда статична, адверсарному поиску предполагается, что среда (противник) активно пытается минимизировать ваш успех. В случае CSP, порядок действий имеет меньшее значение, чем правильность окончательного назначения.
Концептуальный псевдокод: типы агентов
1
# Adversarial Agent (Game Theory)
2
functionDecide_Move(state):
3
returnMaximize_Utility(Predict_Opponent_Minimization(state))
4
5
# CSP Solver (Constraint Logic)
6
functionSolve_CSP(variables, constraints):
7
ifAll_Constraints_Satisfied(assignment):
8
returnassignment
9
else:
10
returnBacktrack_Search(variables)
Course Roadmap
Transitioning from Search (Lesson 2) to Strategic Decision Making (Lesson 3).